A new class of preconditioners for large-scale linear systems from interior-point methods for linear programming

摘要

A new class of preconditioners for the iterative solution of the linear systems arising from interior point methods is proposed. For many of these methods, the linear systems come from applying Newton's method on the perturbed Karush-Kuhn-Tucker optimality conditions for the linear programming problem. This leads to a symmetric indefinite linear system called the augmented system. This system can be reduced to the Schur complement system which is positive definite. After the reduction, the solution for the linear system is usually computed via the Cholesky factorization. This factorization can be dense for some classes of problems. Therefore, the solution of these systems by iterative methods must be considered. Since these systems are very ill-conditioned near a solution of the linear programming problem, it is crucial to develop efficient preconditioners. We show that from the point of view of designing preconditioners, it is better to work with the augmented system. We show that all preconditioners for the Schur complement system have an equivalent for the augmented system while the opposite is not true. The theoretical properties of the new preconditioners are discussed. This class works better near a solution of the linear programming problem when the linear systems are highly ill-conditioned. Another important feature is the option to reduce the preconditioned indefinite system to a positive definite one of the size of the Schur complement. This class of preconditioners relies on the computation of an LU factorization of a subset of columns of the matrix of constraints. The techniques developed for a competitive implementation are rather sophisticated since the subset of columns is not known a priori. The new preconditioner applied to the conjugate gradient method compares favorably with the Cholesky factorization approach. The new approach performs better on large scale problems whose Cholesky factorization contains a large number of nonzero entries. Numerical experiments on several representative classes of linear programming problems are presented to indicate the promise of this new approach.